#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

int dp[52][52][4001];
int opt[52][52][4001];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(m), c(m), d(m);
  for (int i = 0; i < m; i ++) cin >> a[i] >> b[i] >> c[i], d[i] = c[i];
  sort(d.begin(), d.end());
  d.erase(unique(d.begin(), d.end()), d.end());
  for (auto &x : c) x = lower_bound(d.begin(), d.end(), x) - d.begin();
  int P = d.size();
  vector<vector<int>> cnt(n + 1, vector<int>(P));
  for (int l = n; l >= 1; l --) {
    for (int r = l; r <= n; r ++) {
      // cnt: 区间内当 k 是最小值，且价格是 p，有多少车会在 k 洗车
      for (int k = l; k <= r; k ++) {
        fill(cnt[k].begin(), cnt[k].end(), 0);
      }
      for (int i = 0; i < m; i ++) {
        if (a[i] < l || b[i] > r) continue;
        for (int k = a[i]; k <= b[i]; k ++) {
          cnt[k][c[i]]++;
        }
      }
      for (int k = l; k <= r; k ++) {
        for (int p = P - 2; p >= 0; p --) {
          cnt[k][p] += cnt[k][p + 1];
        }
      }

      for (int p = P - 1; p >= 0; p --) {
        for (int k = l; k <= r; k ++) {
          int v = dp[l][k - 1][p] + dp[k + 1][r][p] + cnt[k][p] * d[p];
          if (v > dp[l][r][p]) {
            dp[l][r][p] = v;
            opt[l][r][p] = k;
          }
        }
        if (dp[l][r][p + 1] > dp[l][r][p]) {
          dp[l][r][p] = dp[l][r][p + 1];
          opt[l][r][p] = -1;
        }
      }
    }
  }
  cout << dp[1][n][0] << endl;
  vector<int> ans(n + 1);
  auto dfs = [&](auto &self, int l, int r, int p) {
    if (opt[l][r][p] == 0) return;
    if (opt[l][r][p] == -1) {
      self(self, l, r, p + 1);
      return;
    }
    int k = opt[l][r][p];
    ans[k] = d[p];
    self(self, l, k - 1, p);
    self(self, k + 1, r, p);
  };
  dfs(dfs, 1, n, 0);
  for (int i = 1; i <= n; i ++) {
    cout << (ans[i] ? ans[i] : d.back()) << " ";
  }
  cout << endl;
}